In a database management system (DBMS) executing a transaction that updates, deletes or modifies a body of data, the possibility exists for the transaction to fail (e.g., a communication failure) or for the computer system to fail (e.g., a device failure or a power failure). In either event, it is likely that changes made by one or more committed transactions will not yet have been written to disk, and/or that changes made by one or more uncommitted transactions will have been written to disk.
Transaction failures and computer failures are highly undesirable in a DBMS. One reason why failures in a DBMS can be particularly undesirable is because a DBMS can have hundreds or even thousands of users concurrently accessing and updating data. Changes written to disk by uncommitted transactions that fail can corrupt the database by placing the database in an inconsistent state. Similarly, the database can be corrupted by a failure if changes made by a committed transaction are lost before they are written to disk.
Maintaining log files is one method for protecting data from becoming corrupted by the occurrence of failures. A redo log is a record of changes made by transactions. An undo log is a record of how to undo changes made by transactions. Together, the redo log and the undo log assist in recovery of a DBMS after a failure.
FIG. 1 depicts a recovery process 100 that involves two general phases: a "redo" phase and an "undo" phase. Database 102 needs to be recovered (e.g., a power failure occurred). Prior to the failure, two transactions 132 and 136 performed changes to data contained in database 102. One of those transactions, transaction 132, committed prior to the failure. Transaction 132 is said to have committed because the change(s) completed and were persistently saved to disk in redo log 112, even though the changes themselves were not applied to the database 102. Transaction 136 was also written to redo log 112, which was persistently saved to disk; it too did not get applied to disk. However, transaction 136 did not commit.
Referring to the state of the DBMS depicted in FIG. 1, immediately after the power failure, changes made by committed transaction 132 are not reflected in database 102. However, changes made by a committed transaction must be durable, which means that they must persist on disk even if a failure occurred.
Redo log 112 fixes part of the problem. The redo log 112 contains a series of redo records that save changes made by statements in each transaction. (The redo log 112 may contain data for multiple transactions.) Redo log 112 is temporarily stored in memory and is saved to disk at a regular interval, called a savepoint, or by explicit or implicit instruction from a user or process (e.g., a redo log runs out of space in memory and must flush the redo to disk).
Redo log 112 contains redo records for changes made by committed transaction 132 and uncommitted transaction 136. When the database 102 is recovered, the first step in the recovery process is to apply the redo log 112, specifically, to apply the changes recorded in redo log 112 to database 102. After the redo log 112 has been applied, the database 102 will look like database 104, which reflects the changes made by transactions 132 and 136.
As may be apparent, applying redo log 112 created a problem, specifically, changes made by uncommitted transaction 136 are reflected in database 104. However, changes made by an uncommitted transaction must be removed from the database after a failure occurs. Uncommitted transactions should not be durable. Thus, the data modified by the changes made by transaction 136 is in an inconsistent state. The undo log 120 is designed to fix this problem.
Undo log 120 comprises one or more rollback segments. For example, segment 122 contains data for undoing the changes made by uncommitted transaction 136. After the redo phase, an "undo phase" is performed. During the undo phase, the undo log 120 is used to remove from the database 104 changes that were made to the database 104 by uncommitted transactions. Database 106 is a version of database 104 after applying undo log 120. Notice that changes made by uncommitted transaction 136 are not contained in database 106.
Thus, the changes made by uncommitted transaction 136, which were made when redo log 112 was applied in the redo phase can be "rolled back" using undo log 120 in the undo phase. As uncommitted transaction 136 is rolled back, each change made by transaction 136 is undone, one complete undo record at a time, in an opposite order than the order in which the changes were made.
The undo process described above, whereas simple and predictable, has significant drawbacks. For example, each undo record in the undo log 120 comprises an undo header and a single rollback entry (or "change"). Consequently, when rollback entries in the same undo block store similar information in their headers (e.g., same table space, block identifier, etc.) valuable space is wasted in the undo block. Further, valuable processing resources may also be wasted when generating a header for every rollback entry, as well as when reading the header for every rollback entry.
Further still, the undo records are applied to disk one complete undo record at a time, and then removed from the undo block to prevent the change from being applied more than once. This process further taxes valuable processing cycles.
There is a need for an improved method for applying an undo log.